home *** CD-ROM | disk | FTP | other *** search
/ TPUG - Toronto PET Users Group / TPUG Users Group CD / TPUG Users Group CD.iso / AMIGA / AMICUS / AMICUS22.ADF / BasicSorts / BinarySearch < prev    next >
Text File  |  1987-06-30  |  699b  |  30 lines
  1. '
  2. '  Binary Search for T$ in x$(l..u%)
  3. '     Pre : x$(l..u%) in sorted nondecreasing order
  4. '     Post: p%=0 ->  t$ is not in x(l..u%)
  5. '           p%>0 ->  p% < l+1 and x$(p%) = t$
  6. '     side effects : u% is altered
  7. '
  8.  
  9. SUB BinarySearch ( u%,x$(),t$,p% ) STATIC
  10.  
  11.       l = 1
  12.       Loop:
  13.          IF l > u% THEN p=0 : EXIT SUB
  14.          m% = CINT( ( l + u% ) / 2 )
  15.          IF x$(m%) < t$ THEN l  = m% + 1 : GOTO Loop
  16.          IF x$(m%) > t$ THEN u% = m% - 1 : GOTO Loop
  17.             REM x$(m)=t$
  18.          p%=m%
  19.  
  20. END SUB
  21.  
  22. '
  23. '  Algorithm from Programming Pearls by Jon Bentley
  24. '        from AT&T Bell Laboratories
  25. '
  26. '  Implemented in AmigaBasic by Gregory A. Kendall
  27. '        from Brendallson Software
  28. '
  29.  
  30.